import java.util.*;
class NumMatrix {
    int[][] arr;
    public NumMatrix(int[][] matrix) {
        int row=matrix.length;
        int col=matrix[0].length;
        if(row!=0&&col!=0){
            arr=new int[row][col+1];
        }
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                arr[i][j+1]=matrix[i][j]+arr[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int ret=0;
        for(int i=row1;i<=row2;i++){
            ret+=arr[i][col2+1]-arr[i][col1];
        }
        return ret;
    }
}













class NumMatrix1 {
    public int[][] arr;
    public NumMatrix1(int[][] matrix) {
        int row=matrix.length;
        int col=matrix[0].length;
        if(row!=0&&col!=0){
            arr=new int[row][col+1];
        }
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                arr[i][j+1]=arr[i][j]+matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int ret=0;
        for(int i=row1;i<=row2;i++){
            ret+=arr[i][col2+1]-arr[i][col1];
        }
        return ret;
    }
}














class Solution {
    Map<Integer, List<Integer>> map;
    Random random ;
    public Solution(int[] nums) {
        map=new HashMap<>();
        random=new Random();
        for(int i=0;i<nums.length;i++){
            List<Integer> list=map.getOrDefault(nums[i],new ArrayList<>());
            list.add(i);
            map.put(nums[i],list);
        }
    }

    public int pick(int target) {
        List<Integer> list=map.get(target);
        int size= list.size();
        return random.nextInt(size);
    }
}














public class project {

    public int find(int[] arr,int index){
        if(arr[index]!=index){
            arr[index]=find(arr,arr[index]);
        }
        return arr[index];
    }
    public void union(int[] arr,int l,int r){
        arr[find(arr,l)]=find(arr,r);
    }
    public int[] findRedundantConnection(int[][] edges) {
        int len=edges.length;
        int[] arr=new int[len+1];
        for(int i=1;i<=len;i++){
            arr[i]=i;
        }
        for(int[] edge:edges){
            int l=edge[0];
            int r=edge[1];
            if(find(arr,l)!=find1(arr,r)){
                union(arr,l,r);
            }else{
                return edge;
            }
        }
        return new int[0];
    }




















    public int find1(int[] nums,int index){
        if(nums[index]!=index){
            nums[index]=find1(nums,nums[index]);
        }
        return nums[index];
    }
    public void union1(int[] nums,int l,int r){
        nums[find1(nums,l)]=find1(nums,r);
    }
    public int[] findRedundantConnection1(int[][] edges) {
        int len=edges.length;
        int[] nums=new int[len+1];
        for(int i=1;i<=len;i++){
            nums[i]=i;
        }
        for(int[] edge:edges){
            int l=edge[0];
            int r=edge[1];
            if(find1(nums,l)!=find1(nums,r)){
                union1(nums,l,r);
            }else{
                return edge;
            }
        }
        return new int[0];
    }
}
